package cn.edu.jxau.test;

import java.util.Arrays;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Objects;
import java.util.concurrent.ExecutionException;

public class Main {

	public static void main(String[] args) throws InterruptedException, ExecutionException {

		Node<Integer> root = new Node<>(8);
		root.right = new Node<>(7);
		root.left = new Node<>(8);
		root.left.left = new Node<>(9);
		root.left.right = new Node<>(2);
		root.left.right.left = new Node<>(4);
		root.left.right.right = new Node<>(7);

		Node<Integer> subRoot = new Node<>(8);
		subRoot.left = new Node<>(9);
		subRoot.right = new Node<>(2);

		System.out.println(isSubTree(root, subRoot));
	}

	public static <T extends Comparable<T>> boolean isSubTree(Node<T> root, Node<T> subRoot) {

		if (root == null || subRoot == null) {
			return false;
		}
		boolean result = root.data.compareTo(subRoot.data) == 0;
		if (result) {
			result = match(root, subRoot);
		}
		if (!result) {
			result = isSubTree(root.left, subRoot);
		}
		if (!result) {
			result = isSubTree(root.right, subRoot);
		}
		return result;
	}

	public static <T extends Comparable<T>> boolean match(Node<T> root1, Node<T> root2) {

		if (root2 == null) {
			return true;
		}
		if (root1 == null) {
			return false;
		}
		return match(root1.left, root2.left) && match(root1.right, root2.right);
	}
}

class Node<T> {

	public T data;
	public Node<T> left;
	public Node<T> right;

	public Node() {

	}

	public Node(T data) {
		this.data = data;
	}
}